#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>

 struct Node {
    int val;
    struct Node *next;
    struct Node *random;
  };
  
struct Node* copyRandomList(struct Node* head) 
{
    if(head==NULL)
        return head;
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->next=NULL;
        copy->random=NULL;

        copy->next = cur->next;
        copy->val = cur->val;
        cur->next = copy;
        cur=copy->next;
    } 
    
    cur = head;
    while(cur&&cur->next)
    {
        struct Node* copyhead=cur->next;
        if(cur->random)
            copyhead->random = cur->random->next;
        else
            copyhead->random = NULL;

        cur=cur->next->next;
    }
    cur = head;
    struct Node* copyhead = cur->next;
    while(cur)
    {
        struct Node* copy = cur->next;

        cur->next =copy->next;
        if(cur->next)
            copy->next = cur->next->next;
        else
            copy->next = NULL;
        
        cur = cur->next;
    }
    return copyhead;
}